package com.gaogzhen.algorithms4.foundation;

/**
 *  加权quick-union
 */
public class WeightedQuickUnionUF extends AbstractUnionFind{

    /**
     * 当前触点为根节点树中节点数量
     */
    private int[] size;


    /**
     * 初始化n个触点的数组
     *
     * @param  n 数量n
     */
    public WeightedQuickUnionUF(int n) {
        super(n);
        size = new int[n];
        for (int i = 0; i < n; i++) {
            size[i] = 1;
        }
    }



    /**
     * 返回触点p所在分量标志
     *
     * @param  p 触点p
     * @return 触点p所在分量标志
     */
    public int find(int p) {
        validate(p);
        while (p != getId(p))
            p = getId(p);
        return p;
    }

    /**
     * 合并触点p和触点q所在的分量
     *
     * @param  p 触点p所在分量
     * @param  q 触点p所在分量
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make smaller root point to larger one
        if (size[rootP] < size[rootQ]) {
            setId(rootP, rootQ);
            size[rootQ] += size[rootP];
        }
        else {
            setId(rootQ, rootP);
            size[rootP] += size[rootQ];
        }
        decreaseCount();
    }
}